package 树与图.字典树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 101. 对称二叉树
 *
 * 思路：
 *
 * 对称二叉树是指一棵树的左子树和右子树是镜像对称的。判断一棵树是否对称，可以通过以下步骤实现：
 *
 * 递归比较： 递归比较的是左子树和右子树
 * 	比较左子树的左节点和右子树的右节点。
 * 	比较左子树的右节点和右子树的左节点。
 * 	如果两个节点都为空，则对称。
 * 	如果一个节点为空，另一个不为空，则不对称。
 * 	如果节点值不相同，则不对称。
 *
 * 终止条件：
 * 	当两个节点都为空时，返回 true。
 * 	当一个节点为空，另一个不为空时，返回 false。
 */
public class L_101 {

    public boolean isSymmetric(TreeNode root) {
        if (root == null){
            return true;
        }
        return isSymmetric(root.left,root.right);
    }

    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if(left == null && right == null){
            return true;
        }
        // 如果一个节点为空，另一个节点不为空，则返回false
        if(left == null || right == null){
            return false;
        }
        // 如果节点的左右值不相同，则返回false
        if(left.val != right.val){
            return false;
        }
        return isSymmetric(left.left,right.right) && isSymmetric(left.right,right.left);
    }

    public boolean isSymmetricIteration(TreeNode root) {
        if (root == null){
            return true;
        }
        // 左右子节点必须存在
        if(root.left == null || root.right == null){
            return false;
        }
        // 使用队列模拟递归
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()){
            //弹出左右子节点
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            // 如果两个节点都为空，则继续比较
            if(left == null && right == null){
                continue;
            }
            // 如果两个节点只有一个为空，则返回false
            if(left == null || right == null){
                return false;
            }
            // 如果两个节点的值不相同，则返回false
            if(left.val != right.val){
                return false;
            }

            // 添加下一层节点. 将左子树的左节点和右子树的右节点入队
            queue.offer(left.left);
            queue.offer(right.right);

            // 将左子树的右节点和右子树的左节点入队
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return queue.isEmpty();
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
